#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
//class Solution {
//public:
//    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
//        if (pHead1 == nullptr || pHead2 == nullptr)
//        {
//            if (pHead1)  return pHead1;
//            else  return pHead2;
//        }
//        ListNode* cur1 = pHead1, * cur2 = pHead2;
//        ListNode* newhead = nullptr, * newtail = nullptr;
//        while (cur1 && cur2)
//        {
//            if (cur1->val < cur2->val)
//            {
//                if (newtail == nullptr)
//                {
//                    newtail = newhead = cur1;
//                    cur1 = cur1->next;
//                    newtail->next = nullptr;
//                }
//                else {
//                    newtail->next = cur1;
//                    newtail = newtail->next;
//                    cur1 = cur1->next;
//                    newtail->next = nullptr;
//                }
//            }
//            else {
//                if (newtail == nullptr)
//                {
//                    newtail = newhead = cur2;
//                    cur2 = cur2->next;
//                    newtail->next = nullptr;
//                }
//                else {
//                    newtail->next = cur2;
//                    newtail = newtail->next;
//                    cur2 = cur2->next;
//                    newtail->next = nullptr;
//                }
//            }
//        }
//        if (cur1)  newtail->next = cur1;
//        if (cur2)  newtail->next = cur2;
//        return newhead;
//    }
//};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int src = 0;
        int dst = 0;
        int n = nums.size();
        while (dst < n && src < n)
        {
            while (dst < n && nums[dst] == 0)
            {
                dst++;
            }
            while (src < n && nums[src] != 0)
            {
                src++;
            }
            if (src < n && dst < n && src < dst && nums[src] == 0 && nums[dst] != 0)
                swap(nums[src++], nums[dst++]);
            // else  
            //     break;
        }
    }
};
int main()
{
    vector<int> nums = { 0,1,0,3,12 };
    Solution::moveZeroes(nums);
    return 0;
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cur = 0, dst = -1;
        int n = nums.size();
        while (cur < n)
        {
            if (nums[cur] == 0)  cur++;
            else  swap(nums[++dst], nums[cur++]);
        }
    }
};